package n20;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Main {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put('[', ']');
        map.put('{', '}');
        map.put('(', ')');

        if (s == null || s.length() < 2) {
            return false;
        }
        Deque<Character> q = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            Character peek = q.peek();
            if (peek == null) {
                q.push(c);
                continue;
            }
            Character c1 = map.get(peek);
            if (c1==null){
                continue;
            }
            if ( c1==c ) {
                q.pop();
            } else {
                q.push(c);
            }
        }
        return q.isEmpty();
    }

    public static void main(String[] args) {
        String[] strs = {"()","()[]{}", "(]", "([)]", "{[]}"}; // true, true, false, false, true
        Main main = new Main();
        for (String str : strs) {
            System.out.println(main.isValid(str));
        }
    }
}
